UVa/216 - Getting in line/216.cpp

   1 /*
   2   Accepted
   3  */
   4 #include <cmath>
   5 #include <iostream>
   6 #include <algorithm>
   7 #include <vector>
   8
   9 using namespace std;
  10
  11 int main(){
  12   int n, N=1;
  13   while (cin >> n && n){
  14
  15     vector<pair<int, int> > v(n);
  16     for (int i=0; i<n; ++i){
  17       cin >> v[i].first >> v[i].second;
  18     }
  19     vector<pair<int, int> > solution;
  20     double best = 1E100;
  21
  22     sort(v.begin(), v.end());
  23     do{
  24       double t = 0.0;
  25       for (int i=0; i<n-1; ++i){
  26         t += hypot(v[i].first-v[i+1].first, v[i].second-v[i+1].second) + 16.0;
  27       }
  28       if (t < best){
  29         solution = v;
  30         best = t;
  31       }
  32     }while(next_permutation(v.begin(), v.end()));
  33
  34     printf("**********************************************************\n");
  35     printf("Network #%d\n", N++);
  36     for (int i=0; i<n-1; ++i){
  37       printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.\n",
  38              solution[i].first, solution[i].second,
  39              solution[i+1].first, solution[i+1].second,
  40              hypot(solution[i].first - solution[i+1].first,
  41                    solution[i].second - solution[i+1].second) + 16.0);
  42     }
  43     printf("Number of feet of cable required is %.2f.\n", best);
  44   }
  45   return 0;
  46 }